// 有N种物品和一个容量为V的背包，第i种物品最多有`M[i]`件可用，耗费的空间是`C[i]`,价值是`M[i]`,
// 求解将哪些物品装入背包可以使这些物品的耗费的空间总和不超过背包容量，且价值总和最大
// 多重背包和01背包非常像，把`M[i]`件摊开其实就是一个01背包问题

let inputArr = [
    [10, 3],
    [1, 3, 4],
    [15, 20, 30],
    [2, 3, 2]
]

function fun(inputArr) {
    let [C, N] = inputArr[0] // C是背包容量
    let weight = inputArr[1] // 耗费的空间
    let value = inputArr[2] // 价值
    let k = inputArr[3] // 最多有几件
    let w = []
    let v = []
    for (let i = 0; i < k.length; i++) {
        let count = k[i]
        while (count) {
            w.push(weight[i])
            v.push(value[i])
            // 注意这里
            count--
        }        
    }
    let dp = new Array(C + 1).fill(0)
    for (let i = 0; i < w.length; i++) {
        for (let j = C; j >= w[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i])            
        }        
    }
    return dp[C]
}

console.log(fun(inputArr))